package ClassicDataStructuresAndAlgorithms.ClassicLinkedListAlgorithms;

/**
 * 判断回文链表
 * 可以使用链表的逆序递归，来模拟双指针
 */

/**
 * 使用我们原来的方法一太笨了，而且使用空间较多。
 * 我们使用方法二。
 * 首先通过快慢指针，找出链表中点的后一位。
 * 将以中点为首的那部分链表翻转
 * 最后从两边往中间遍历并且比较元素是否相同
 */

public class Solution234 {

    public boolean isPalindrome(ListNode head) {
        //先找出链表中点的后一位,使用快慢指针技巧
        ListNode slow = head;
        ListNode fast = head;

        while(fast!=null && fast.next!=null){
            slow=slow.next;
            fast = fast.next.next;
        }

        //若fast不为null，说明链表为奇数链表
        //此时slow指向正中间的元素，还得手动调整，向后一位
        if (fast!=null){
            slow = slow.next;
        }

        //将以slow为首的那部分链表反转
        ListNode left = head;
        ListNode right = reverse(slow);

        while(right!=null){
            if (left.val != right.val){
                return false;
            }
            left = left.next;
            right = right.next;
        }

        return true;

    }

    public ListNode reverse(ListNode head){

        ListNode pre = null;
        ListNode cur = head;
        ListNode nxt = head.next;

        while(cur!=null){
            cur.next = pre;
            pre = cur;
            cur = nxt;
            if (nxt!=null){
                nxt = nxt.next;
            }
        }

        return pre;
    }



    public static void main(String[] args) {
        ListNode p1 = new ListNode(1);
        ListNode p2 = new ListNode(2);
        ListNode p3 = new ListNode(2);
        ListNode p4 = new ListNode(1);
        p1.next = p2;p2.next = p3;p3.next = p4;
        Solution234 solution234 = new Solution234();
        boolean palindrome = solution234.isPalindrome(p1);
        System.out.println("palindrome = " + palindrome);
    }
}
